package com.zhugang.week09;

/**
 * @program algorithms
 * @description: movingCount2
 * @author: chanzhugang
 * @create: 2022/08/22 22:10
 */
public class MovingCount2 {

    /**
     * 面试题13 机器人的运动范围
     *
     * @param m
     * @param n
     * @param k
     * @return
     */
    private boolean[][] visited;
    private int count;

    public int movingCount(int m, int n, int k) {
        // 二位矩阵：图上的DFS
        visited = new boolean[m][n];
        dfs(0, 0, m, n, k);
        return count;
    }

    private void dfs(int i, int j, int m, int n, int k) {
        visited[i][j] = true;
        count++;
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int di = 0; di < 4; di++) {
            int newi = i + directions[di][0];
            int newj = j + directions[di][0];
            if (newi >= m || newi < 0 || newj >= n || newj < 0 || visited[newi][newj] == true || check(newi, newj, k) == false) {
                continue;
            }
            dfs(newi, newj, m, n, k);
        }
    }

    /**
     * 行、列坐标数位之和与k比较
     *
     * @param i
     * @param j
     * @param k
     * @return
     */
    private boolean check(int i, int j, int k) {
        int sum = 0;
        while (i != 0) {
            sum += i % 10;
            i /= 10;
        }
        while (j != 0) {
            sum += j % 10;
            j /= 10;
        }
        return sum <= k;
    }
}